package com.wtgroup.demo.mianshi.算法.动态规划.背包问题;

import com.wtgroup.demo.common.util.Tools;
import org.junit.Test;

/**
 * @author 60906
 * @date 2021/5/12 15:22
 */
public class D_01背包 {
    @Test
    public void foo1() {
        int[] w = {2, 3, 4, 7};
        int[] v = {1, 3, 5, 9};
        int bag = 10;
        // int res = new Solution_Rec().process(w, v, bag);
        // System.out.println(res);
        // int res2 = new Solution_RecDp().process(w, v, bag);
        // System.out.println(res2);
        int res3 = new Solution_T().run(w, v, bag);
        System.out.println(res3);
        int res4 = new Solution_T2().run(w, v, bag);
        System.out.println(res4);
    }


    // 暴力递归 --> 动态规划
    class Solution_T {

        int run(int[] w, int[] v, int bag) {
            // index, rest ==> dp[][]
            int N = w.length;
            int[][] dp = new int[N+1][bag + 1];
            // 填 dp
            for (int index = N-1 ; index >= 0; index--) {
                for (int rest = 1; rest <= bag; rest++) {
                    dp[index][rest] = dp[index + 1][rest];
                    if (rest >= w[index]) {
                        int yes = v[index] + dp[index + 1][rest - w[index]];
                        dp[index][rest] = yes >= dp[index][rest] ? yes : dp[index][rest];
                    }
                }
            }

            for (int i = 0; i < dp.length; i++) {
                Tools.printArray(dp[i]);
            }

            return dp[0][bag];
        }
    }

    // 数组压缩
    class Solution_T2 {

        int run(int[] w, int[] v, int bag) {
            // index, rest ==> dp[][]
            int N = w.length;
            int[] dp = new int[bag + 1];
            // 填 dp
            for (int index = N-1 ; index >= 0; index--) {
                for (int rest = bag; rest >= 1; rest--) {
                    dp[rest] = dp[rest];
                    if (rest >= w[index]) {
                        int yes = v[index] + dp[rest - w[index]];
                        dp[rest] = yes >= dp[rest] ? yes : dp[rest];
                    }
                }
            }

            return dp[bag];
        }
    }









    /**
     * 只考虑当前位置物品, 取?不取?
     */
    class Solution_Rec {
        /**
         *
         * @param w 物品体积
         * @param v 价值
         * @param index 当前物品
         * @param bag 包容量
         * @return
         */
        int process(int[] w, int[] v, int bag) {

            return func(w, v, 0, bag);
        }

        // 可变参数: index(当前商品下标), rest(包的剩余容量)
        private int func(int[] w, int[] v, int index, int rest) {
            if (rest <= 0 || index >= w.length) {
                return 0;
            }

            // 不取
            int ans = func(w, v, index + 1, rest);
            // 取
            if (w[index] <= rest) {
                int p2 = v[index] + func(w, v, index + 1, rest - w[index]);
                ans = Math.max(ans, p2);
            }

            return ans;
        }
    }

    /**
     * 暴力递归-->动归
     */
    class Solution_RecDp {
        int process(int[] w, int[] v, int bag) {
            int[][] dp = new int[w.length + 1][bag + 1];
            // dp[w.length][..] == 0
            for (int index = w.length-1; index >= 0; index--) {
                for (int rest = 1; rest <= bag; rest++) {
                    if (w[index] <= rest) {
                        dp[index][rest] = Math.max(dp[index + 1][rest], v[index] + dp[index + 1][rest - w[index]]);
                    } else {
                        dp[index][rest] = dp[index + 1][rest];
                    }
                }
            }

            for (int i = 0; i < dp.length; i++) {
                Tools.printArray(dp[i]);
            }

            return dp[0][bag];
        }
    }
}
